home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Mac Power 1996 October
/
MACPOWER-1996-10.ISO.7z
/
MACPOWER-1996-10.ISO
/
AMUG
/
Internet_31
/
NetCacheResolver 0.9d6
/
NetCacheResolver 0.9d6 ト
/
library
/
NCR_Qsort.c
< prev
next >
Wrap
Text File
|
1996-05-12
|
8KB
|
255 lines
// NetCache Resolver, 1995 (C) Mizutori Tetsuya
// - NCR_Qsort.c, October 18, 1995
// This document is pretty printed in 10-point Geneva font.
#include "NCR_Basic.h"
#include "NCR_Qsort.h"
#include "NCR_Error.h"
#ifdef DEBUG
#include "NCR_Message.h"
#endif /*DEBUG */
// prototype
static void swap ( Array *a, long i, long j );
static short compare ( Array *a, long i, long j, Boolean asNumber );
static short compareAsNumber ( Array *a, long i, long j );
static short compareAsAlphabet ( Array *a, long i, long j );
static long ValueAsNumber ( unsigned char *p, long maxlen );
// constants
static unsigned char charmap[] = {
'¥000', '¥001', '¥002', '¥003', '¥004', '¥005', '¥006', '¥007', // control
'¥010', '¥011', '¥012', '¥013', '¥014', '¥015', '¥016', '¥017',
'¥020', '¥021', '¥022', '¥023', '¥024', '¥025', '¥026', '¥027',
'¥030', '¥031', '¥032', '¥033', '¥034', '¥035', '¥036', '¥037',
'¥040', '¥041', '¥042', '¥043', '¥044', '¥045', '¥046', '¥047', // " !..."
'¥050', '¥051', '¥052', '¥053', '¥054', '¥055', '¥056', '¥057', // "()*+,-./"
'¥060', '¥061', '¥062', '¥063', '¥064', '¥065', '¥066', '¥067', // "01234567"
'¥070', '¥071', '¥072', '¥073', '¥074', '¥075', '¥076', '¥077', // "89:;<=>?"
'¥100', '¥141', '¥142', '¥143', '¥144', '¥145', '¥146', '¥147', // "@A..."
'¥150', '¥151', '¥152', '¥153', '¥154', '¥155', '¥156', '¥157', // "HI..."
'¥160', '¥161', '¥162', '¥163', '¥164', '¥165', '¥166', '¥167', // "PQ..."
'¥170', '¥171', '¥172', '¥133', '¥134', '¥135', '¥136', '¥137', // "XY..."
'¥140', '¥141', '¥142', '¥143', '¥144', '¥145', '¥146', '¥147', // "`a..."
'¥150', '¥151', '¥152', '¥153', '¥154', '¥155', '¥156', '¥157', // "hi..."
'¥160', '¥161', '¥162', '¥163', '¥164', '¥165', '¥166', '¥167', // "pq..."
'¥170', '¥171', '¥172', '¥173', '¥174', '¥175', '¥176', '¥177', // "xy..."
'¥141', '¥141', '¥143', '¥145', '¥156', '¥157', '¥165', '¥141',
'¥141', '¥141', '¥141', '¥141', '¥141', '¥143', '¥145', '¥145',
'¥145', '¥145', '¥151', '¥151', '¥151', '¥151', '¥156', '¥157',
'¥157', '¥157', '¥157', '¥157', '¥165', '¥165', '¥165', '¥165',
'¥240', '¥241', '¥242', '¥243', '¥244', '¥245', '¥246', '¥247',
'¥250', '¥251', '¥252', '¥253', '¥254', '¥255', '¥256', '¥257',
'¥260', '¥261', '¥262', '¥263', '¥264', '¥265', '¥266', '¥267',
'¥270', '¥271', '¥272', '¥273', '¥274', '¥275', '¥276', '¥277',
'¥300', '¥301', '¥302', '¥303', '¥304', '¥305', '¥306', '¥307',
'¥310', '¥311', '¥040', '¥141', '¥141', '¥157', '¥316', '¥317',
'¥320', '¥321', '¥322', '¥323', '¥324', '¥325', '¥326', '¥327',
'¥171', '¥171', '¥332', '¥333', '¥334', '¥335', '¥336', '¥337',
'¥340', '¥341', '¥342', '¥343', '¥344', '¥141', '¥145', '¥141',
'¥145', '¥145', '¥151', '¥151', '¥151', '¥151', '¥157', '¥157',
'¥360', '¥157', '¥165', '¥165', '¥165', '¥365', '¥366', '¥367',
'¥370', '¥371', '¥372', '¥373', '¥374', '¥375', '¥376', '¥377',
};
/***** Quick Sort *****/
void qsort ( Array *a, long left, long right, Boolean asNumber, Boolean inReverse )
{
long i, last;
if ( left >= right ) return;
swap( a, left, (right+left)/2 );
last = left;
for ( i=left+1; i<=right; i++ )
#ifdef COMMENT
if ( inReverse ) {
for ( i=left+1; i<=right; i++ )
if ( compare( a, left, i, asNumber ) < 0 ) swap( a, ++last, i );
} else {
for ( i=left+1; i<=right; i++ )
if ( compare( a, left, i, asNumber ) > 0 ) swap( a, ++last, i );
}
#else /* COMMENT */
if ( ((compare( a, left, i, asNumber ) > 0) ^ inReverse ) != 0 ) swap( a, ++last, i );
#endif /* COMMENT */
swap( a, left, last );
qsort( a, left, last-1, asNumber, inReverse );
qsort( a, last+1, right, asNumber, inReverse );
}
static void swap ( Array *a, long i, long j )
{
ArrayPair pair;
pair = a->pair[i];
a->pair[i] = a->pair[j];
a->pair[j] = pair;
}
static short compare ( Array *a, long i, long j, Boolean asNumber )
{
if ( asNumber )
return compareAsNumber(a, i, j );
else
return compareAsAlphabet( a, i, j );
}
static short compareAsAlphabet ( Array *a, long i, long j )
{
register unsigned char * cm = (unsigned char *) charmap;
register unsigned char *d, *s;
register long k;
long dlen, slen, min;
short result;
dlen = (a->pair[i]).keywordlen;
slen = (a->pair[j]).keywordlen;
min = ( dlen < slen ? dlen : slen );
d = ((unsigned char *) *(a->h)) + (a->pair[i]).keyword;
s = ((unsigned char *) *(a->h)) + (a->pair[j]).keyword;
k = 0;
while ( k < min ) {
if ( cm[d[k]] != cm[s[k]] ) break;
k++;
}
if ( k >= min ) result = dlen - slen;
else result = ((unsigned short) cm[d[k]]) - ((unsigned short)cm[s[k]]);
return ( ( result > 0 ) ? ( 1 ) : ( result==0 ? 0 : -1 ) );
}
static short compareAsNumber ( Array *a, long i, long j )
{
long dval, sval;
long dlen, slen;
long result;
dlen = (a->pair[i]).keywordlen;
slen = (a->pair[j]).keywordlen;
dval = ValueAsNumber( ((unsigned char *) *(a->h)) + (a->pair[i]).keyword, dlen );
sval = ValueAsNumber( ((unsigned char *) *(a->h)) + (a->pair[j]).keyword, slen );
result = dval - sval;
return ( ( result > 0 ) ? ( 1 ) : ( result==0 ? 0 : -1 ) );
}
#ifdef COMMENT
static short compare ( Array *a, long i, long j )
{
register unsigned char * cm = (unsigned char *) charmap;
register unsigned char *d;
register unsigned char *s;
short result;
d = ((unsigned char *) *(a->h)) + i;
s = ((unsigned char *) *(a->h)) + j;
while ( ( *d != EOS ) && ( *s != EOS ) ) {
if ( cm[*d] != cm[*s] ) break;
++d; ++s; }
result = ((unsigned short) cm[*d]) - ((unsigned short)cm[*s]);
return ( (result)>0 ? 1 : ( (result)==0 ) ? 0 : -1 );
}
#endif /* COMMENT */
static long ValueAsNumber ( unsigned char *p, long maxlen )
{
register long s = 0;
register long i = 0;
register unsigned char c;
Boolean isMinus = false;
while ( p[i] == ' ' ) { i++; }
while ( p[i] == '-' ) { isMinus = ! isMinus; i++; }
while ( p[i] == ' ' ) { i++; }
while ( (c=p[i]) >= '0' && c <= '9' && i < maxlen ) { s = 10*s + (c-'0'); i++; }
if ( isMinus ) s = -s;
return s;
}
/***** Splitting Fields of Record *****/
#define EOL '¥r'
#define TAB '¥t'
// On calling SetupFieldArray(), please set the '.fs' and '.rs' field of 'arrayH'.
long SetupFieldArray ( Handle dataH, ArrayHandle arrayH, short keyPosition )
{
register unsigned char *p, *q;
unsigned long i, j, k, len;
long datasize, count=0;
short countKey;
short FS = TAB, RS = EOL;
OSErr err;
// setup Field Separator and Record Separator
if ( ((Array *) *arrayH)->fs != '¥0' ) FS = ((Array *) *arrayH)->fs;
if ( ((Array *) *arrayH)->rs != '¥0' ) RS = ((Array *) *arrayH)->rs;
HLock( dataH );
datasize = GetHandleSize( dataH );
p = (unsigned char *) *dataH;
SetHandleSize( (Handle) arrayH, sizeof( Array ) );
if ( (err=MemError()) != noErr ) { ErrorMessageMEM( err, true ); }
i = 0; count = 0;
while ( i < datasize ) {
j = i;
while ( j<datasize && p[j] != RS ) j++;
SetHandleSize( (Handle) arrayH, GetHandleSize((Handle) arrayH)+sizeof(ArrayPair) );
if ( (err=MemError()) != noErr ) { ErrorMessageMEM( err, true ); }
((Array *) *arrayH)->pair[count].text = i;
((Array *) *arrayH)->pair[count].textlen = j-i;
count++;
i = j+1;
}
if ( count > 0 ) for ( k=0; k<count; k++ ) {
q = p + ((Array *) *arrayH)->pair[k].text;
len = ((Array *) *arrayH)->pair[k].textlen;
if ( keyPosition <= 0 ) {
((Array *) *arrayH)->pair[k].keyword = (q-p);
((Array *) *arrayH)->pair[k].keywordlen = len;
} else {
i = 0; countKey= 1;
while ( i < len && countKey < keyPosition )
if ( q[i++] == FS ) countKey++;
j = i;
while (j < len && q[j] != FS ) j++;
((Array *) *arrayH)->pair[k].keyword = (q-p) + i;
((Array *) *arrayH)->pair[k].keywordlen = j-i;
}
}
out:
((Array *) *arrayH)->h = dataH;
((Array *) *arrayH)->count = count;
HUnlock( dataH );
return count;
}
// end of program